package com.zjj.lbw.interview.tree;

import com.zjj.lbw.interview.common.TreeNode;

import java.util.*;

/**
 * @author zhanglei.zjj
 * @description 二叉树层序遍历
 * @date 2023/9/3 17:04
 */
public class BinaryTreeLevelOrder {

    /**
     * @param root 本次递归节点
     * @param list 保存输出结果的容器
     * @param i    不呢递归的节点在list容器中的下标位置
     */
    public static void LevelOrderRecursion(TreeNode root, List<Integer> list, int i) {
        if (root == null) {
            return;
        }

        // 由于使用list的set方法进行索引位置元素替换，因此先要提前保证要操作的索引位置初始化完成
        int k = list.size();
        if (k <= i) {
            for (int j = k; j <= i; j++) {
                list.add(j, null);
            }
        }
        list.set(i, root.val);
        // 当前父节点为i，则左子节点编号(根节点从1开始编号)为 2 * i，右子节点为 2 * i + 1
        LevelOrderRecursion(root.left, list, 2 * i);
        LevelOrderRecursion(root.right, list, 2 * i + 1);

    }

    /**
     * 二叉树层序遍历-迭代
     * @param root
     */
    public static void LevelOrderIteration(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode headNode = queue.poll();
            if (headNode != null) {
                System.out.println(headNode.val);
                queue.add(headNode.left);
                queue.add(headNode.right);
            }
        }
    }

    public static void main(String[] args) {
        TreeNode node7 = new TreeNode(7, null, null);
        TreeNode node6 = new TreeNode(6, null, null);
        TreeNode node5 = new TreeNode(5, node6, node7);
        TreeNode node4 = new TreeNode(4, null, null);
        TreeNode node3 = new TreeNode(3, null, null);
        TreeNode node2 = new TreeNode(2, node4, node5);
        TreeNode node1 = new TreeNode(1, node2, node3);

        ArrayList<Integer> list = new ArrayList<>();
        LevelOrderRecursion(node1, list, 1);
        list.remove(null);
        System.out.println(Arrays.toString(list.toArray()));

        LevelOrderIteration(node1);
    }
}
